package Graph;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;
import java.util.Stack;

public class Dijkstra {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        //n个点
        int n = scanner.nextInt();
        //传入起点位置
        int start = scanner.nextInt();
        //创建邻接矩阵
        int[][] cap = new int[n][n];
        //初始化为最大值
        for (int i = 0; i < n; i++) {
            Arrays.fill(cap[i],Integer.MAX_VALUE);
        }
        //输入为一些路径若不规定双向,比如0 1 10 表示0到1的单向距离是10
        //输入t表示接下来要输入t 条边，每一行0 1 10 表示0到1的单向距离是10
        int t = scanner.nextInt();
        while(t-->0){
            int row = scanner.nextInt();
            int col = scanner.nextInt();
            int distance = scanner.nextInt();
            cap[row][col] = distance;
        }
        //现在输入完毕，输出当前图的最小路径。以start为开始位置.
        int[] dist = new int[n]; //记录单源到每个点的最短路径的长度
        int[] path = new int[n]; //记录当前从某点到某点的最短路径，存放的是某点起点的顶点信息
//        ArrayList<Integer> s = new ArrayList<>(n);  //记录已经确定的最短路径的结点集合
        int[] s = new int[n];
        //初始化 dist和path数组
        for (int i = 0; i < n; i++) {
            dist[i] = cap[start][i];
            if(dist[i]!=Integer.MAX_VALUE){
                path[i] = start;
            }else{
                path[i] = -1;
            }
        }
        s[start] = 1;  //顶点代表集合，1代表在集合中，0代表不在

        for (int i = 1; i < n; i++) {
            int min = findMinDist(s,dist); //dist中查找s[i]=0的最小值距离
            s[min] = 1; //将新生成的终点加入集合S
            for (int j = 0; j < n; j++) {
                //更新数组dist 和 path
                if(s[j]==0 && (dist[j] > dist[min] + cap[min][j])){
                    dist[i] = dist[min] + cap[min][j];  //用已经找到的最短路径修改对应的dist
                    path[i] = min;  //用已经找到的最短路径修改对应的path
                }
            }
        }
        displayPath(dist,path,s,start,n);


    }

    //打印起始点到个顶点最短距离
    private static void displayPath(int[] dist, int[] path, int[] s, int start, int n) {
        for (int i = 0; i < n; i++) {
            if(i==start){
                System.out.println(i);
            }else{
                int tmp = i;
                Stack<Integer> stack = new Stack<>();
                while(tmp!=start){
                    stack.push(path[tmp]);
                    tmp = path[tmp];
                }
                while(!stack.isEmpty()){
                    System.out.print(stack.pop()+"->");
                }
                System.out.println(i);

            }

        }
    }

    public static int findMinDist(int[] s, int[] dist){
        int min = Integer.MAX_VALUE;
        int index = 0;
        for (int i = 0; i < s.length; i++) {
            if(s[i]==0){
                if(min > dist[i] && dist[i] != 0 && dist[i] != Integer.MAX_VALUE){
                    index = i;  //记录最小值下标
                    min = dist[i];  //取小值
                }
            }
        }
        return index;
    }

}
